// O(logn)
int hammingWeight(unsigned long n) {
    int s = 0;
    while(n>0){
        s = s + n % 2;
        n = n / 2;
    }
    return s;
}


/* O(M), M是1的个数
* n-1 最右边的1变成0，该1右边的零变成1
* n&(n-1) 最右边的1变成0
*/
int hammingWeight(unsigned long n) {
    int res = 0;
    while(n){
        n &= n - 1;
        res ++;
    }
    return res;
}